// 哈希表
// 通常在无序的数组中 快速查找元素 需要用到哈希表
// 使用数组模拟简易哈希表
// 可以将问题转化成找一个数就可以用哈希表
// 可以用哈希表判断是否是字母异位词：统计字符串里面字符的个数进行对比

// 例题 5：
// 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
//
//        字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
//
//        示例 1:
//
//        输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//        输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
//        示例 2:
//
//        输入: strs = [""]
//        输出: [[""]]
//        示例 3:
//
//        输入: strs = ["a"]
//        输出: [["a"]]
//
//
//        提示：
//
//        1 <= strs.length <= 104
//        0 <= strs[i].length <= 100
//        strs[i] 仅包含小写字母

// 解题思路：
// 识别字母异位词，将词排序，然后通过和哈希表的 key 对比来实现
// 排序后的字符串作为哈希表的 key，将 List<String> 作为值进行存储
// 找到每个词对应的 key，将该词作为 List<String> 的值放在哈希表中，就实现了分组

import java.util.*;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        int n = strs.length;
        for(int i = 0; i < n; i++){
            String tmp = strs[i];
            char[] t = tmp.toCharArray();
            Arrays.sort(t);
            String s = new String(t);
            if(!map.containsKey(s)) map.put(s, new ArrayList<>());
            map.get(s).add(tmp);
        }
        List<List<String>> ret = new ArrayList<>();
        for(Map.Entry<String, List<String>> entry : map.entrySet()) ret.add(entry.getValue());
        //for(String s : map.keySet()) ret.add(map.get(s));
        return ret;
    }
}
